Corelab Seminar
2006-2007
Valia Mitsou (NTUA)
Distributed leader election algorithms in synchronous networks
Abstract. Leader election is the problem of finding a unique leader in a network of processors, in the sense that the leader (the specified processor) knows that has been elected and all the other processors know that they have not been elected. In some other versions it might also be required that all the non-leader processes learn who the leader is. There exists a broad range of leader election algorithms. These algorithms have different message complexity in worst and average case. Furthermore, they vary in communication mechanism (asynchronous vs synchronous), processor names (unique identities vs anonymous), network topology (example ring, tree, complete graph or arbitrary graph) and others. Leader election is one of the most fundamental problems in distributed computing and has a numerous of applications. For example it is an important tool for breaking symmetry in a distributed system. By choosing a processor as the leader, it is possible to execute centralized protocols in a decentralized environment. Leader election can also be used to recover from token loss for token-based protocols, by making the leader responsible for generating a new token when the current one is lost.
Material. Slides [pdf].